#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void print(int *a, int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void Swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}

// 冒泡排序
void BubbleSort(int *a, int size)
{
    for(int i = 0; i < size - 1; i++)   // 要整理的数的最大次数
    {
        int flag = 0;
        for(int j = 0; j < size - i - 1; j++)   // 单轮冒泡比较的次数
        {
            if(a[j] > a[j+1])
            {
                flag = 1;
                Swap(&a[j], &a[j+1]);
            }
        }
        if(flag == 0)   //遍历数列没有任何两个数需要交换，说明已经有序
        {
            break;
        }
    }
}

// 插入排序（要背！！！）
void InsertSort(int *a, int size)
{
    for(int i = 0; i < size; i++)   // 插入的数据个数
    {
        int j = i;  // i是要插入的数据的下标
        int temp = a[i];
        for(; j > 0; j--)
        {
            if(a[j-1] > temp)
                a[j] = a[j-1];  // 比要插入的数大的数就往后挪
            else
                break;
        }
        a[j] = temp; 
    }
}

// 选择排序
#if 0
    void ChooseSort(int *a, int size)
    {
        for(int i = 0; i < size - 1; i++)
        {
            int min = i;
            for(int j = i + 1; j < size; j++)
            {
                if(a[min] > a[j])
                {
                    min = j;
                }
            }
            Swap(&a[i], &a[min]);
        }
    }
#endif

#if 1
    // 双指针算法
    void ChooseSor2(int *a, int size)
    {
        for(int left = 0, right = size - 1; left < right; left++, right--)
        {
           int min = left, max = right;
           for(int i = left; i <= right; i++)
           {
                if(a[min] > a[i])
                {
                    min = i;
                }
                if(a[max] < a[i])
                {
                    max = i;
                }
           }
           Swap(&a[left], &a[min]);
           // 极值正好都在两边
           if(max == left)
           {
                max = min;
           }
           Swap(&a[right], &a[max]);
        }
    }
#endif


